package com.daybyday.day1.day9;

import com.sun.deploy.util.StringUtils;

import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
import javax.swing.*;
import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.sql.Time;
import java.sql.Timestamp;
import java.text.SimpleDateFormat;
import java.util.*;
import java.util.concurrent.TimeUnit;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2021/2/4

*/
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }


 }

public class Solution {
    static ArrayList<Integer> list = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    public static void main(String[] args) throws Exception {

        Solution s = new Solution();
      Map<String,Object> map = new HashMap<>();
      map.put("offset",0);
      map.put("limit",10);
        System.out.println(map.toString());

    }

    public static String HMACSHA256(String data, String key) throws Exception {
        Mac sha256_HMAC = Mac.getInstance("HmacSHA256");
        SecretKeySpec secret_key = new SecretKeySpec(key.getBytes("UTF-8"), "HmacSHA256");
        sha256_HMAC.init(secret_key);
        byte[] array = sha256_HMAC.doFinal(data.getBytes("UTF-8"));
        StringBuilder sb = new StringBuilder();
        for (byte item : array) {
            sb.append(Integer.toHexString((item & 0xFF) | 0x100).substring(1, 3));
        }
        return sb.toString().toLowerCase();
    }

    public static String toHexString(String s){
        String str="";
        for (int i=0;i<s.length();i++){
            int ch = (int)s.charAt(i);
            String s4 = Integer.toHexString(ch);
            str = str + s4;
        }
        return str;
    }
      public static String getSHA256(String str){
        MessageDigest messageDigest;

       String encodestr = "";
       try {
           messageDigest = MessageDigest.getInstance("SHA-256");
           messageDigest.update(str.getBytes("UTF-8"));
           encodestr = byte2HexString(messageDigest.digest());
       } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
       } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
       }
       return encodestr.toLowerCase();
      }
      public static String byte2Hex(byte[] bytes){
        StringBuffer stringBuffer = new StringBuffer();
        String tmp = null;
          for (int i = 0; i < bytes.length; i++) {
              tmp = Integer.toHexString(bytes[i]&0xFF);
              if(tmp.length() == 1){
                  stringBuffer.append("0");
              }
              stringBuffer.append(tmp);
          }
          return stringBuffer.toString();
      }



    public static final char[] DIGITS_UPPER = { '0', '1', '2', '3', '4', '5',
            '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };

    public static String byte2HexString(final byte[] data) {
        final int l = data.length;
        final char[] out = new char[l << 1];
        // two characters form the hex value.
        for (int i = 0, j = 0; i < l; i++) {
            out[j++] = DIGITS_UPPER[(0xF0 & data[i]) >>> 4];
            out[j++] = DIGITS_UPPER[0x0F & data[i]];
        }
        return new String(out);
    }
    public int countNums(int num){
        int count = 0;
        while(num != 0){
            if(num % 3 == 0){
                num /= 3;
            }else if((num - 1) % 3 == 0){
                 num -= 1;
            }else{
                num -= 1;
            }
            count++;
        }
        return count;
    }
    public static boolean dgfs(TreeNode root,int n,ListNode tmp){
        if(root == null){
            return false;
        }
        tmp.next = new ListNode(root.val);
        if(n == root.val){
            return true;
        }else{
            if(dgfs(root.left,n,tmp.next)){
                return true;
            }

            if(dgfs(root.right,n,tmp.next)){
                return true;
            }
        }

        return false;

    }

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        /*如果只有一个节点，那么他就是最小高度树*/
        if (n == 1) {
            res.add(0);
            return res;
        }
        /*建立各个节点的出度表*/
        int[] degree = new int[n];
        /*建立图关系，在每个节点的list中存储相连节点*/
        List<List<Integer>> map = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            map.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;/*出度++*/
            map.get(edge[0]).add(edge[1]);/*添加相邻节点*/
            map.get(edge[1]).add(edge[0]);
        }
        /*建立队列*/
        Queue<Integer> queue = new LinkedList<>();
        /*把所有出度为1的节点，也就是叶子节点入队*/
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) queue.offer(i);
        }
        /*循环条件当然是经典的不空判断*/
        while (!queue.isEmpty()) {
            res = new ArrayList<>();/*这个地方注意，我们每层循环都要new一个新的结果集合，
            这样最后保存的就是最终的最小高度树了*/
            int size = queue.size();/*这是每一层的节点的数量*/
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                res.add(cur);/*把当前节点加入结果集，不要有疑问，为什么当前只是叶子节点为什么要加入结果集呢?
                因为我们每次循环都会新建一个list，所以最后保存的就是最后一个状态下的叶子节点，
                这也是很多题解里面所说的剪掉叶子节点的部分，你可以想象一下图，每层遍历完，
                都会把该层（也就是叶子节点层）这一层从队列中移除掉，
                不就相当于把原来的图给剪掉一圈叶子节点，形成一个缩小的新的图吗*/
                List<Integer> neighbors = map.get(cur);
                /*这里就是经典的bfs了，把当前节点的相邻接点都拿出来，
                 * 把它们的出度都减1，因为当前节点已经不存在了，所以，
                 * 它的相邻节点们就有可能变成叶子节点*/
                for (int neighbor : neighbors) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1) {
                        /*如果是叶子节点我们就入队*/
                        queue.offer(neighbor);
                    }
                }
            }
        }
        return res;
    }


    public List<String> topKFrequent(String[] words, int k) {
        List<String> res = new ArrayList<>();
        Map<String, Integer> map = new TreeMap<>();
        for (String word : words) {
           int size =  map.get(word) == null ? 1 : map.get(word) + 1;
           map.put(word,size);
        }
        String[][] result = new String[map.size()][2];
        int i = 0;
        for (String s : map.keySet()) {
            result[i][0] = s;
            result[i++][1] = map.get(s)+"";
        }
        Arrays.sort(result, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                return Integer.parseInt(o2[1]) - Integer.parseInt(o1[1]);
            }
        });
        for (int j = 0; j < k; j++) {
            res.add(result[j][0]);
        }
        return res;
    }

        int ans;
    public int longestUnivaluePath(TreeNode root) {
        ans = 0;
        arrowLength(root);
        return ans;
    }

    public int arrowLength(TreeNode node){
        if (node == null) return 0;
        int left = arrowLength(node.left);
        int righ = arrowLength(node.right);

        int arrowLeft = 0;int arrowRight = 0;
        if (node.left != null && node.left.val == node.val){
            arrowLeft += left + 1;
        }
        if (node.right != null && node.right.val == node.val){
            arrowRight += righ + 1;
        }
        ans = Math.max(ans, arrowLeft + arrowRight);
        return Math.max(arrowLeft,arrowRight);
    }
    public int repeatedStringMatch(String a, String b) {
        int res = -1;
        int tmp = 0;
        int n = a.length();int m = b.length();int pos = 0;
        int start = pos;
        if(n >= m){
            if (a.contains(b)){
                return 1;
            }else if ((a + a).contains(b)){
                return 2;
            }else{
                return -1;
            }
        }
        res = 1;
        while (tmp < m){
            if (a.charAt(pos) != b.charAt(tmp)){
                pos = ++ start;
                if (start == n) return -1;
                if (!a.contains(b.charAt(tmp)+"")) return -1;
                tmp = 0;
                continue;
            }
            tmp ++;
            pos ++;
            if (pos == n && tmp < m){
                pos = 0;
                res++;
            }
        }
        return res;
    }

    public int movesToMakeZigzag(int[] nums) {
        int oonum = 0;
        int subnum = 0;
        int[] nums2 = Arrays.copyOf(nums,nums.length);
        for (int i = 0; i < nums.length - 1; i++) {
            if ((i & 1) == 0){
                if(nums[i] <= nums[i + 1]){
                   oonum += nums[i + 1] - nums[i] + 1;
                   nums[i + 1] -= nums[i + 1] - nums[i] + 1;
                }
            }else{
                if (nums[i] >= nums[i + 1]){
                    oonum += nums[i] - nums[i + 1] + 1;
                    nums[i] -= nums[i] - nums[i + 1] + 1;
                }
            }
        }

        for (int i = 0; i < nums2.length - 1; i++) {
            if ((i & 1) == 0){
                if(nums2[i] >= nums2[i + 1]){
                    subnum += nums2[i] - nums2[i + 1] + 1;
                    nums2[i] -= nums2[i] - nums2[i + 1] + 1;
                }
            }else{
                if (nums2[i] <= nums2[i + 1]){
                    subnum += nums2[i + 1] - nums2[i] + 1;
                    nums2[i + 1] -= nums2[i + 1] - nums2[i] + 1;
                }
            }
        }
        return Math.min(oonum,subnum);
    }

    public int deepestLeavesSum(TreeNode root) {
        int sum = 0;
        List<Integer> list = new LinkedList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        queue.addLast(null);
        while (queue.size() > 1){
            TreeNode treeNode = queue.removeFirst();
            if (treeNode == null){
                list.add(sum);
                sum = 0;
                queue.addLast(null);
            }else{
                if (treeNode.left != null) queue.addLast(treeNode.left);
                if (treeNode.right != null) queue.addLast(treeNode.right);
                sum += treeNode.val;
            }


        }
        list.add(sum);
        return list.get(list.size() - 1);
    }

    public boolean checkValidString(String s) {
        char[] chars = s.toCharArray();
        Stack<Integer> left = new Stack<>();
        Stack<Integer> mini = new Stack<>();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(')left.push(i);
            if (chars[i] == '*')mini.push(i);
            if (chars[i] == ')'){
                if (left.size() > 0){
                    left.pop();
                }else if (mini.size() > 0){
                    mini.pop();
                }else{
                    return false;
                }
            }
        }
        if (left.size() > mini.size()) return false;
        while (left.size() > 0 && mini.size()>0){
            if (left.pop() > mini.pop()) return false;
        }
        return true;
    }




}
